1. 题目描述（中等难度）

[warning] 222. 完全二叉树的节点个数

2. 解法一:递归

递归遍历二叉树，统计节点个数

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     preOrder(root,list);
     return list.size();
    }

    public void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
}

简单递归实现

public int countNodes(TreeNode root) {
    if (root == null){
        return 0;
    }
    return countNodes(root.left) + countNodes(root.right) + 1;
}

3. 解法二：迭代

使用栈进行迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Deque<TreeNode> deque = new ArrayDeque<>();
      while(!deque.isEmpty() || root != null){
          while(root != null){
              res.add(root.val);
              deque.offerLast(root);
              root = root.left;
          }
         root =  deque.pollLast();
         root = root.right;
      }
      return res.size();
    }
}

4. 解法三：迭代+位运算

递归与迭代时间复杂度不太理想，进阶采用更快的时间复杂度解决，根据完成二叉树的性质解决问题。

完全二叉树定义：它是一棵空树或者它的叶子节点只出在最后两层，若最后一层不满则叶子节点只在最左侧。

满二叉树的节点个数计算方式：层数h, 则节点个数为 2^h - 1

对 root 节点的左右子树进行高度统计，分别记为 left 和 right，有以下两种结果

• left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是 2^left - 1，加上当前这个 root 节点，则正好是 2^left。再对右子树进行递归统计。
• left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点 +root 节点，总数为 2^right。再对左子树进行递归查找。

二叉树的层数计算方式

    private int countLevel(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(countLevel(root.left), countLevel(root.right)) + 1;
    }

二叉树左子树或右子树层数计算

    public int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            level++;
            root = root.left;
        }
        return level;
    }

注意： 1<<left 是 (int)Math.pow(2,leftLevel)的高级写法，2^left 次方。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
       if(root == null){
           return 0;
       }
      int leftLevel = level(root.left);
      int rightLevel = level(root.right);
      if(leftLevel == rightLevel){
          return (int)Math.pow(2,leftLevel) + countNodes(root.right);
      }
      else{
          return (int)Math.pow(2,rightLevel) + countNodes(root.left);
      }
    }
    public int level(TreeNode root){
        int count = 0;
        while(root != null){
            count++;
            root = root.left;
        }
        return count;
    }
}